﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MadLibrary.Collections
{
    /// <summary>A class representing a binaric search tree.</summary>
    /// <remarks>
    /// If T is IComparable of implements it, the <see cref="System.IComparable.CompareTo"/> method
    /// will be used for sorting, otherwised, the hashcode of the object will be used.
    /// </remarks>
    /// <typeparam name="T">The type of objects to be sorted.</typeparam>
    public class BinarySearchTree<T> : IEnumerable<T>, ICollection<T>
    {
        internal static bool IsNull(object a)
        {
            return (a as object) == null;
        }

        private readonly Func<T, T, int> comparer;
        private int? cacheCount = 0, cacheHeight = 0, cacheLeafCount = 0;
        private BinarySearchNode<T> root;

        /// <summary>
        /// Constructs a BinarySearchTree with the given items.
        /// </summary>
        /// <param name="args"></param>
        public BinarySearchTree(params T[] args)
        {
            if (typeof(T).GetInterface("IComparable") != null)
                comparer = (a, b) =>
                {
                    return (a as IComparable).CompareTo((b as IComparable));
                };
            else
                comparer = (a, b) =>
                {
                    return a.GetHashCode().CompareTo(b.GetHashCode());
                };
            foreach (var i in args)
                Add(i, ref root);
        }

        #region Add Methods

        /// <summary>
        /// Adds an item to the tree.
        /// </summary>
        /// <param name="item">The item to add to the tree.</param>
        /// <returns>A number indecating the nesting level of the node.</returns>
        public int Add(T item)
        {
            if (Equals(item, null))
                return -1;
            cacheCount = cacheHeight = cacheLeafCount = null;
            return Add(item, ref root);
        }

        internal int Add(T item, ref BinarySearchNode<T> node)
        {
            if (node == null)
            {
                node = new BinarySearchNode<T>(item);
                return 0;
            }
            int cmp = comparer(item, node.Value);
            if (cmp < 0)
                return 1 + Add(item, ref node.leftNode);
            return 1 + Add(item, ref node.rightNode);
        }

        internal int Add(BinarySearchNode<T> item, ref BinarySearchNode<T> node)
        {
            if (item == null)
                return 0;
            if (node == null)
            {
                node = item;
                return 0;
            }
            int cmp = comparer(item.Value, node.Value);
            if (cmp < 0)
                return 1 + Add(item, ref node.leftNode);
            return 1 + Add(item, ref node.rightNode);
        }

        #endregion Add Methods

        #region Remove Methods

        /// <summary>
        /// Removes the first instance of the given item from the tree.
        /// </summary>
        /// <param name="item">The item to remove from the tree.</param>
        /// <returns>True if item removed successfully, false otherwise.</returns>
        public bool Remove(T item)
        {
            if (root == null)
                return false;

            if (Equals(root.Value, item))
            {
                var left = root.LeftNode;
                root = root.RightNode;
                Add(left, ref root);
            }

            bool ans = _remove(ref root, item);
            if (ans)
                cacheCount = cacheHeight = cacheLeafCount = null;
            return ans;
        }

        private bool _remove(ref BinarySearchNode<T> node, T item)
        {
            if (node == null)
                return false;
            if (Equals(node.Value, item))
            {
                var left = node.leftNode;
                var right = node.rightNode;
                node = null;
                Add(left, ref right);
                Add(right, ref root);
                return true;
            }
            bool result = _remove(ref node.leftNode, item);
            if (result)
                return true;
            return _remove(ref node.rightNode, item);
        }

        #endregion Remove Methods

        #region Properties

        /// <summary>
        /// Gets the height of the binary tree.
        /// </summary>
        public int Height
        {
            get
            {
                return cacheHeight ?? (cacheHeight = root.Height).Value;
            }
        }

        /// <summary>
        /// Gets the number of nodes are in the tree.
        /// </summary>
        public int Count
        {
            get
            {
                if (root == null)
                    return 0;
                return cacheCount ?? (cacheCount = root.Count).Value;
            }
        }

        /// <summary>
        /// Gets the number of nodes of type 'Leaf' in this tree.
        /// </summary>
        public int CountLeaf
        {
            get
            {
                if (root == null)
                    return 0;
                return cacheLeafCount ?? (cacheLeafCount = root.CountLeaf).Value;
            }
        }

        /// <summary>
        /// Determines if the collection is read only
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        #endregion Properties

        #region Misc interface implementations

        /// <summary>
        /// Gets the <see cref="System.Collections.IEnumerator"/> of this collection
        /// </summary>
        /// <returns></returns>
        public IEnumerator<T> GetEnumerator()
        {
            if (root == null)
                yield break;
            foreach (var val in root.Enumerate())
                yield return val;
            yield break;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        void ICollection<T>.Add(T item)
        {
            Add(item);
        }

        /// <summary>
        /// Clears the tree and deletes all nodes.
        /// </summary>
        public void Clear()
        {
            root = null;
        }

        /// <summary>
        /// Determines if the specified item is in the tree.
        /// </summary>
        /// <param name="item">The item to search for.</param>
        /// <returns>True if the item is found, false otherwise.</returns>
        public bool Contains(T item)
        {
            return Contains(item, root);
        }

        internal bool Contains(T item, BinarySearchNode<T> node)
        {
            if (node == null) return false;

            int cmp = comparer(item, node.Value);
            if (cmp == 0)
                return true;
            if (cmp == -1)
                return Contains(item, node.LeftNode);
            return Contains(item, node.RightNode);
        }

        /// <summary>
        /// Copies the elements of the tree to the given array starting from the given index.
        /// </summary>
        /// <param name="array">The array to copy to.</param>
        /// <param name="arrayIndex">The initial index in which the copy begins.</param>
        public void CopyTo(T[] array, int arrayIndex)
        {
            int maxItems = array.Length - arrayIndex;
            foreach (T t in this)
            {
                array[arrayIndex++] = t;
                if (maxItems-- < 0)
                    break;
            }
        }

        #endregion Misc interface implementations

        #region Inner types

        /// <summary>
        /// An enum containing the types of nodes in a binary tree.
        /// </summary>
        public enum BinarySearchNodeType
        {
            /// <summary>
            /// A leaf node is a node with no children
            /// </summary>
            Leaf,

            /// <summary>
            /// A branch node is a node with one child or more.
            /// </summary>
            Branch
        }

        /// <summary>A class represnting a node in a binary search tree.</summary>
        /// <typeparam name="T">The type of values used in the tree.</typeparam>
        public class BinarySearchNode<T>
        {
            internal T value; 
            internal BinarySearchNode<T> leftNode;
            internal BinarySearchNode<T> rightNode;

            /// <summary>
            /// Builds a new instance of a BinarySearchNode
            /// </summary>
            /// <param name="value">The value of the node</param>
            public BinarySearchNode(T value)
            {
                Value = value;
            }

            /// <summary>
            /// Gets the left child node of this node.
            /// </summary>
            public BinarySearchNode<T> LeftNode
            {
                get { return leftNode; }
                internal set { leftNode = value; }
            }

            /// <summary>
            /// Gets the right child node of this node.
            /// </summary>
            public BinarySearchNode<T> RightNode
            {
                get { return rightNode; }
                internal set { rightNode = value; }
            }

            /// <summary>
            /// Gets the value of this node.
            /// </summary>
            public T Value
            {
                get { return this.value; }
                internal set { this.value = value; }
            }

            /// <summary>
            /// Gets the type of this node.
            /// </summary>
            public BinarySearchNodeType NodeType
            {
                get
                {
                    if (leftNode == null && rightNode == null)
                        return BinarySearchNodeType.Leaf;
                    return BinarySearchNodeType.Branch;
                }
            }

            /// <summary>
            /// Gets the height of this node from the bottom of the tree.
            /// </summary>
            public int Height
            {
                get
                {
                    if (this.NodeType == BinarySearchNodeType.Leaf)
                        return 1;
                    if (leftNode == null ^ rightNode == null)
                    {
                        return 1 + (leftNode ?? rightNode).Height;
                    }
                    return 1 + System.Math.Max(leftNode.Height, rightNode.Height);
                }
            }

            /// <summary>
            /// Gets the count of nodes including this node and all child nodes to the bottom of the tree.
            /// </summary>
            public int Count
            {
                get
                {
                    int c = 1;
                    if (leftNode != null)
                        c += leftNode.Count;
                    if (rightNode != null)
                        c += rightNode.Count;
                    return c;
                }
            }

            /// <summary>
            /// Gets the hashcode of the value of the node.
            /// </summary>
            /// <returns>A <see cref="System.Int32"/> represnting the hashcode of the value of the node.</returns>
            public override int GetHashCode()
            {
                return Value.GetHashCode();
            }

            /// <summary>
            /// Determines whether the specified <see cref="System.Object"/> is equal to the current <see cref="System.Object"/>.
            /// </summary>
            /// <param name="obj"></param>
            /// <returns></returns>
            public override bool Equals(object obj)
            {
                return Value.Equals(obj);
            }

            /// <summary>
            /// Reaturns a string represnting this node and its contents.
            /// </summary>
            /// <returns>A <see cref="System.String"/> with the contents of this node.</returns>
            public override string ToString()
            {
                return string.Format("Value: '{0}'", Value);
            }

            /// <summary>
            /// Determines if both given nodes are equal.
            /// </summary>
            public static bool operator ==(BinarySearchNode<T> a, BinarySearchNode<T> b)
            {
                if (BinarySearchTree<T>.IsNull(a) && BinarySearchTree<T>.IsNull(b))
                    return true;
                else if (BinarySearchTree<T>.IsNull(a))
                    return false;
                return (a ?? new BinarySearchNode<T>(default(T))).Equals(b);
            }

            /// <summary>
            /// Determines if both given nodes are not equal.
            /// </summary>
            public static bool operator !=(BinarySearchNode<T> a, BinarySearchNode<T> b)
            {
                return !(a == b);
            }

            /// <summary>
            /// Returns an <see cref="System.Collections.IEnumerable"/> containing all sub values of this node.
            /// </summary>
            /// <returns></returns>
            internal IEnumerable<T> Enumerate()
            {
                if (LeftNode != null)
                    foreach (var item in LeftNode.Enumerate())
                        yield return item;

                yield return Value;

                if (RightNode != null)
                    foreach (var item in RightNode.Enumerate())
                        yield return item;
                yield break;
            }

            /// <summary>
            /// Gets the number of leaves under this node.
            /// </summary>
            public int CountLeaf
            {
                get
                {
                    if (this.NodeType == BinarySearchNodeType.Leaf)
                        return 1;
                    int c = 0;
                    if (leftNode != null)
                        c += leftNode.CountLeaf;
                    if (rightNode != null)
                        c += rightNode.CountLeaf;
                    return c;
                }
            }
        }

        #endregion Inner types
    }
}